package structures.search;

import java.util.Arrays;
import java.util.Stack;

// 二分查找(要求数组是有序的)
public class BinarySearch {

    private static final int[] dataArray1 =
            {2, 3, 3, 6, 6, 6, 7, 9, 9, 9, 10, 10, 13, 15, 15, 16, 16, 18, 19, 19};
    private static final int[] dataArray2 =
            {0, 1, 1, 2, 6, 6, 6, 8, 10, 10, 11, 13, 14, 14, 15, 15, 15, 17, 17};

    private static final int VALUE = 19;

    public static void main(String[] args) {
        // 查找数据
        int index = binarySearch(dataArray1, VALUE, 0, dataArray1.length);
        if (index != -1) {
            System.out.println("---- 找到数据索引值： " + index + " ----");
        } else {
            System.out.println("---- 未找到数据 ----");
        }

        Stack<Integer> retArray = new Stack<>();
        binarySearch(dataArray1, VALUE, 0, dataArray1.length, retArray);
        while (!retArray.isEmpty()) {
            System.out.print(retArray.pop() + "\t");
        }
        System.out.println();
    }

    /**
     * 二分法查找
     * @param dataArray 有序数据源
     * @param value 需要查找的值
     * @param start 开始位置
     * @param end   结束为止 + 1
     * @return
     */
    private static int binarySearch(int[] dataArray, int value, int start, int end) {
        int mid = (start + end) / 2;

        if (start >= end) {
            return -1;
        }

        if (dataArray[mid] == value) {
            return mid;
        }

        if ((dataArray[mid] > value)) {
            return binarySearch(dataArray, value, start, mid);
        }

        if ((dataArray[mid] < value)) {
            return binarySearch(dataArray, value, mid + 1, end);
        }

        return -1;
    }

    private static void binarySearch(int[] dataArray, int value, int start, int end, Stack<Integer> retArray) {
        int mid = (start + end) / 2;

        if (start >= end) {
            return;
        }

        if (dataArray[mid] == value) {
            retArray.push(mid);

            int temp = mid - 1;
            while (temp >= 0 && dataArray[temp] == value) {
                retArray.push(temp--);
            }

            temp = mid + 1;
            while (temp < end && dataArray[temp] == value) {
                retArray.push(temp++);
            }

            return;
        }

        if ((dataArray[mid] > value)) {
            binarySearch(dataArray, value, start, mid, retArray);
        }

        if ((dataArray[mid] < value)) {
            binarySearch(dataArray, value, mid + 1, end, retArray);
        }
    }
}
